{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Bitwise ORs of Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subarrayBitwiseORs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #子数组按位或操作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们有一个非负整数数组<meta charset=\"UTF-8\" />&nbsp;<code>arr</code>&nbsp;。</p>\n",
    "\n",
    "<p>对于每个（连续的）子数组<meta charset=\"UTF-8\" />&nbsp;<code>sub = [arr[i], arr[i + 1], ..., arr[j]]</code>&nbsp;（&nbsp;<code>i &lt;= j</code>），我们对<meta charset=\"UTF-8\" />&nbsp;<code>sub</code>&nbsp;中的每个元素进行按位或操作，获得结果<meta charset=\"UTF-8\" />&nbsp;<code>arr[i] | arr[i + 1] | ... | arr[j]</code>&nbsp;。</p>\n",
    "\n",
    "<p>返回可能结果的数量。 多次出现的结果在最终答案中仅计算一次。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [0]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>\n",
    "只有一个可能的结果 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,1,2]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>\n",
    "可能的子数组为 [1]，[1]，[2]，[1, 1]，[1, 2]，[1, 1, 2]。\n",
    "产生的结果为 1，1，2，1，3，3 。\n",
    "有三个唯一值，所以答案是 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例&nbsp;3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2,4]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "可能的结果是 1，2，3，4，6，以及 7 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong><meta charset=\"UTF-8\" /></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i]&nbsp;&lt;= 10<sup>9</sup></code>​​​​​​​</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [bitwise-ors-of-subarrays](https://leetcode.cn/problems/bitwise-ors-of-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [bitwise-ors-of-subarrays](https://leetcode.cn/problems/bitwise-ors-of-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0]', '[1,1,2]', '[1,2,4]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        a = 0\n",
    "        for i in arr:\n",
    "            a |= i\n",
    "        n = len(arr)\n",
    "        l = set()\n",
    "        l.add(a)\n",
    "        for i in range(n):\n",
    "            tmp = arr[i]\n",
    "            l.add(tmp)\n",
    "            if tmp == a:\n",
    "                continue\n",
    "            for j in range(i + 1,n):\n",
    "                tmp |= arr[j]\n",
    "                l.add(tmp)\n",
    "                if tmp == a:\n",
    "                    break\n",
    "        return len(l)\n",
    "s = Solution()\n",
    "print(s.subarrayBitwiseORs([1, 1, 2]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        ors = []\n",
    "        n = len(arr)\n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            ors.append(0)\n",
    "            num = arr[i]\n",
    "            for j in range(len(ors)):\n",
    "                ors[j] |= num\n",
    "            k = 0\n",
    "            for j in range(len(ors)):\n",
    "                if ors[j] != ors[k]:\n",
    "                    k += 1\n",
    "                    ors[k] = ors[j]\n",
    "            del ors[k+1:]\n",
    "            for x in ors:\n",
    "                ans.add(x)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        a = []\n",
    "        res = set()\n",
    "        for i,x in enumerate(arr):\n",
    "            a.append([arr[i],i])\n",
    "           \n",
    "            k = 0\n",
    "            for p in a:\n",
    "                p[0] |= x\n",
    "                if p[0] == a[k][0]:\n",
    "                    a[k][1] = i\n",
    "                else:\n",
    "                    k += 1\n",
    "                    a[k] = p\n",
    "            del a[k+1:]\n",
    "            for p in a:\n",
    "                res.add(p[0])\n",
    "        \n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ors = []\n",
    "        ans = set()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = arr[i]\n",
    "            ors.append(0)\n",
    "            k = 0\n",
    "            for j in range(len(ors)):\n",
    "                ors[j] |= x\n",
    "                if ors[k] != ors[j]:\n",
    "                    k += 1\n",
    "                    ors[k] = ors[j]\n",
    "            del ors[k+1:]\n",
    "            # print(ors)\n",
    "            for num in ors:\n",
    "                ans.add(num)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        s = set()\n",
    "        ors = []\n",
    "        n = len(arr)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = arr[i]\n",
    "            ors.append([0, i])\n",
    "            k = 0 \n",
    "            for p in ors:\n",
    "                p[0] |= x \n",
    "                if ors[k][0] == p[0]:\n",
    "                    ors[k][1] = p[1]\n",
    "                else:\n",
    "                    k += 1\n",
    "                    ors[k] = p \n",
    "            del ors[k + 1:]\n",
    "            for o in ors:\n",
    "                s.add(o[0])\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        st=[]\n",
    "        res=set()\n",
    "        for i,a in enumerate(arr):\n",
    "            for j in range(len(st)):\n",
    "                st[j][0]=st[j][0]|a\n",
    "            nst=[]\n",
    "            for v,j in st:\n",
    "                if len(nst)==0 or v!=nst[-1][0]:\n",
    "                    nst.append([v,j])\n",
    "                    res.add(v)\n",
    "            nst.append([a,i])\n",
    "            res.add(a)\n",
    "            st=nst\n",
    "            if len(st)>1 and st[-1][0]==st[-2][0]:\n",
    "                st.pop()\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        if len(arr) == 1:\n",
    "            return 1\n",
    "        # mask = (1 << 31) - 1\n",
    "        mask = 0\n",
    "\n",
    "        for a in arr:\n",
    "            mask |= a\n",
    "        \n",
    "        # 30, 111111111\n",
    "\n",
    "        seen = set()\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            tmp = 0\n",
    "            for j in range(i, len(arr)):\n",
    "                tmp |= arr[j]\n",
    "                seen.add(tmp)\n",
    "\n",
    "                if tmp == mask:\n",
    "                    break\n",
    "\n",
    "        return len(seen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        ors = []\n",
    "        s = set()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            num = nums[i]\n",
    "            ors.append([0,i])\n",
    "            k = 0\n",
    "            for o in ors:\n",
    "                o[0] |= num\n",
    "                if o[0] == ors[k][0]:\n",
    "                    ors[k][1] = o[1]\n",
    "                else:\n",
    "                    k+=1\n",
    "                    ors[k] = o\n",
    "            del ors[k+1:]\n",
    "            for a,b in ors:\n",
    "                s.add(a)\n",
    "            # print(ors)\n",
    "            ans[i] = ors[0][1]-i+1\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        for i, x in enumerate(arr):\n",
    "            ans.add(x)\n",
    "            for j in range(i-1, -1, -1):\n",
    "                tmp = arr[j] | x\n",
    "                if tmp == arr[j]:\n",
    "                    break\n",
    "                arr[j] = tmp\n",
    "                ans.add(tmp)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        mask = 0\n",
    "        for x in arr:\n",
    "            mask |= x\n",
    "\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            curr = arr[i]\n",
    "            for j in range(i, n):\n",
    "                curr |= arr[j]\n",
    "                s.add(curr)\n",
    "                if curr == mask:\n",
    "                    break\n",
    "\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        pre = set()\n",
    "        pre.add(arr[0])\n",
    "        lens = len(arr)\n",
    "        ans = set()\n",
    "        ans.add(arr[0])\n",
    "        for i in range(1,lens):\n",
    "            now = set()\n",
    "            num = arr[i]\n",
    "            now.add(num)\n",
    "            ans.add(num)\n",
    "            for p in pre:\n",
    "                now.add(p | num)\n",
    "                ans.add(p | num)\n",
    "            pre = now\n",
    "        \n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        res=set()\n",
    "        max_val=max(arr)\n",
    "        num=len(bin(max_val))-2\n",
    "        tmp=2**num-1\n",
    "        for i in range(n):\n",
    "            res.add(arr[i])\n",
    "            ss=arr[i]\n",
    "            j=i-1\n",
    "            while j>=0 and ss<tmp:\n",
    "                ss|=arr[j]\n",
    "                res.add(ss)\n",
    "                j-=1\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res=0\n",
    "        vis=set()\n",
    "        ors = []  # 按位或的值 + 对应子数组的右端点的最小值\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            num = nums[i]\n",
    "            ors.append([0, i])\n",
    "            k = 0\n",
    "            for p in ors:\n",
    "                p[0] |= num\n",
    "                if p[0] not in vis:\n",
    "                    vis.add(p[0])\n",
    "                    res+=1\n",
    "                if ors[k][0] == p[0]:\n",
    "                    ors[k][1] = p[1]  # 合并相同值，下标取最小的\n",
    "                else:\n",
    "                    k += 1\n",
    "                    ors[k] = p\n",
    "            del ors[k + 1:]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        ors = []\n",
    "        s = set()\n",
    "\n",
    "        for i,x in enumerate(arr):\n",
    "            ors.append(0)\n",
    "            k = 0\n",
    "            for j in range(len(ors)):\n",
    "                ors[j]|=x\n",
    "                if ors[j]==ors[k]:\n",
    "                    continue\n",
    "                else: \n",
    "                    k+=1\n",
    "                    ors[k]=ors[j]\n",
    "            del ors[k+1:]\n",
    "            for num in ors:\n",
    "                s.add(num)\n",
    "        return len(s)\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        book = set()\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            if(arr[i] not in book):\n",
    "                book.add(arr[i])\n",
    "                result += 1\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if(arr[i] | arr[j] == arr[j]):\n",
    "                    break\n",
    "                arr[j] = arr[i] | arr[j]\n",
    "                if(arr[j] not in book):\n",
    "                    book.add(arr[j])\n",
    "                    result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        cur = set([arr[0]])\n",
    "\n",
    "        for i in range(len(arr)):\n",
    "            nxt = set()\n",
    "            for elem in cur:\n",
    "                nxt.add(elem | arr[i])\n",
    "            nxt.add(arr[i])\n",
    "            cur = nxt\n",
    "            ans |= nxt\n",
    "        return len(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        cur = {0}\n",
    "        for x in arr:\n",
    "            cur = {x | y for y in cur} | {x}\n",
    "            ans |= cur\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        # ans = set()\n",
    "        ans = set() \n",
    "        cur = {0}\n",
    "        for ai in arr:\n",
    "            cur = {ai|y for y in cur} | {ai}\n",
    "            ans |= cur\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        cur = {0}\n",
    "        ans = set()\n",
    "        for x in arr:\n",
    "            cur = {x|y for y in cur} | {x}\n",
    "            ans |= cur\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        if len(arr) == 1:\n",
    "            return 1\n",
    "        ans = set()\n",
    "        pre = set()\n",
    "        for j in range(len(arr)):\n",
    "            cur = set()\n",
    "            cur.add(arr[j])\n",
    "\n",
    "            for ele in pre:\n",
    "                cur.add(ele | arr[j])\n",
    "            \n",
    "            ans |= cur\n",
    "            pre = cur\n",
    "        \n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        res = set()\n",
    "        cur = set()\n",
    "\n",
    "        for num in arr:\n",
    "            new_set = {num}\n",
    "            for c in cur:\n",
    "                new_set.add(num | c)\n",
    "            cur = new_set\n",
    "            res.update(cur)\n",
    "        \n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        current_set = set()\n",
    "        result = set()\n",
    "\n",
    "        for num in arr:\n",
    "            current_set.add(num)\n",
    "            temp_set = set()\n",
    "            for val in current_set:\n",
    "                temp_set.add(val | num)\n",
    "            result |= temp_set\n",
    "            current_set = temp_set\n",
    "\n",
    "        return len(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def subarrayBitwiseORs(self, A):\n",
    "        ans = set()\n",
    "        cur = {0}\n",
    "        for x in A:\n",
    "            cur = {x | y for y in cur} | {x}\n",
    "            ans |= cur\n",
    "        return len(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        cur = {0}\n",
    "        for x in arr:\n",
    "            cur = {x | y for y in cur} | {x}\n",
    "            ans |= cur\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        seen = set()\n",
    "        level = set()\n",
    "        for num in arr:\n",
    "            level = {prev | num for prev in level} | {num}\n",
    "            seen |= level\n",
    "        return len(seen)\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        pre = {0}\n",
    "        for x in arr:\n",
    "            pre = set(x | y for y in pre)\n",
    "            pre.add(x)\n",
    "            ans.update(pre)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        res = set()\n",
    "        cur = set()\n",
    "        for a in arr:\n",
    "            temp = set()\n",
    "            for n in cur:\n",
    "            # cur = {a | y for y in cur} | {a}\n",
    "                temp.add(a|n)\n",
    "            temp.add(a)\n",
    "            res |= temp\n",
    "            cur = temp\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        ors = set()\n",
    "        for x in arr:\n",
    "            ors = {o|x for o in ors}\n",
    "            ors.add(x)\n",
    "            ans |= ors\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        ans = set()\n",
    "        ors = set()\n",
    "        for x in arr:\n",
    "            ors = {i | x for i in ors}\n",
    "            ors.add(x)\n",
    "            ans |= ors\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        pre = set()\n",
    "        for num in arr:\n",
    "            cur = {num | p for p in pre} | {num}\n",
    "            ans |= cur\n",
    "            pre = cur\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def subarrayBitwiseORs(self, arr):\n",
    "        ans = set()\n",
    "        cur = {0}\n",
    "        for x in arr:\n",
    "            cur = {x | y for y in cur} | {x}\n",
    "            ans |= cur\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        res = set()\n",
    "        cur = set()\n",
    "        for a in arr:\n",
    "            # temp = set()\n",
    "            # for n in cur:\n",
    "            cur = {a | y for y in cur} | {a}\n",
    "            # temp.add(a)\n",
    "            res |= cur\n",
    "            # cur = temp\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        cur = {0}\n",
    "        for i in range(len(arr)):\n",
    "            cur = {arr[i] | y for y in cur} | {arr[i]}\n",
    "            ans |=cur\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        cur = {0}\n",
    "        for x in arr:\n",
    "            cur = {x | y for y in cur} | {x}\n",
    "            ans |= cur\n",
    "        return len(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        ors=[]\n",
    "        res=set()\n",
    "        for i in range(n-1,-1,-1):\n",
    "            ors.append(0)\n",
    "            ors2=[]\n",
    "            for v in ors:\n",
    "                ors2.append(v|arr[i])\n",
    "            ors=list(set(ors2))\n",
    "            res|=set(ors2)\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def subarrayBitwiseORs(self, A):\n",
    "        ans = set()\n",
    "        cur = {0}\n",
    "        for x in A:\n",
    "            cur = {x | y for y in cur} | {x}\n",
    "            ans |= cur\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        cur = {0}\n",
    "        for x in arr:\n",
    "            cur = {x | y for y in cur} | {x}\n",
    "            ans |= cur\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        res = set()\n",
    "        cur = {0}\n",
    "        for x in arr:\n",
    "            cur = {x | y for y in cur} | {x}\n",
    "            res |= cur\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        res = set()\n",
    "        cur = {0}\n",
    "        for x in arr:\n",
    "            cur = {x | y for y in cur} | {x}\n",
    "            res |= cur\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        res = set()\n",
    "        cur = {0}\n",
    "        for x in arr:\n",
    "            cur = {x | y for y in cur} | {x}\n",
    "            res |= cur\n",
    "        return len(res)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        cur = {0}\n",
    "        for x in arr:\n",
    "            cur = {x | y for y in cur} | {x}\n",
    "            ans |= cur\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        ors = set()\n",
    "        n = len(arr)\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            x = arr[i]\n",
    "            ors.add(0)\n",
    "            ors = set([k | x for k in ors])\n",
    "            ans |= ors\n",
    "        return len(ans)\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        cur = set()\n",
    "        for val in arr:\n",
    "            tmp = set()\n",
    "            for cur_i in cur:\n",
    "                tmp.add(cur_i | val)\n",
    "            tmp.add(val)\n",
    "            cur = tmp\n",
    "            ans |= tmp\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res=set()\n",
    "        ors=set()\n",
    "        for x in nums:\n",
    "            ors={x|num for num in ors}\n",
    "            ors.add(x)\n",
    "            res|=ors\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        ors = set()\n",
    "        n = len(arr)\n",
    "        for x in arr:\n",
    "            ors.add(0)\n",
    "            ors = {k | x for k in ors}\n",
    "            ans |= ors\n",
    "        return len(ans)\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        cur, res = set(), set()\n",
    "        for a in arr:\n",
    "            cur = {n | a for n in cur} | {a}\n",
    "            res |= cur\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        ors = set()\n",
    "        for x in arr:\n",
    "            ors = {o | x for o in ors}\n",
    "            ors.add(x)\n",
    "            ans |= ors\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def subarrayBitwiseORs(self, A):\n",
    "        ans = set()\n",
    "        cur = {0}\n",
    "        for x in A:\n",
    "            cur = {x | y for y in cur} | {x}\n",
    "            ans |= cur\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = [0] * n\n",
    "        val_idx = []  # 按位或的值 + 对应子数组的右端点的最小值\n",
    "        s = set()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            num = nums[i]\n",
    "            val_idx.append([0, i])\n",
    "            k = 0\n",
    "            for p in val_idx:\n",
    "                p[0] |= num\n",
    "                if val_idx[k][0] == p[0]:\n",
    "                    val_idx[k][1] = p[1]  # 合并相同值，下标取最小的\n",
    "                else:\n",
    "                    k += 1\n",
    "                    val_idx[k] = p\n",
    "            del val_idx[k + 1:]\n",
    "            # 本题只用到了 val_idx[0]，如果题目改成任意给定数值，可以在 val_idx 中查找\n",
    "            ans[i] = val_idx[0][1] - i + 1\n",
    "            s |= set([x[0] for x in val_idx])\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        # ans = set()\n",
    "        ans = set() \n",
    "        cur = {0}\n",
    "        for ai in arr:\n",
    "            cur = {ai|y for y in cur} | {ai}\n",
    "            ans |= cur\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\r\n",
    "        ans=set()\r\n",
    "        cur={0}\r\n",
    "        for x in arr:\r\n",
    "            cur={x|y for y in cur} | {x}\r\n",
    "            ans|=cur\r\n",
    "        return len(ans)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def subarrayBitwiseORs(self, A):\n",
    "        ans = set()\n",
    "        cur = {0}\n",
    "        for x in A:\n",
    "            cur = {x | y for y in cur} | {x}\n",
    "            ans |= cur\n",
    "        return len(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        cur = set()\n",
    "        for a in arr:\n",
    "            cur = {x | a for x in cur} | {a}\n",
    "            ans |= cur  \n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        ans = set()\n",
    "        pre = set()\n",
    "        for num in arr:\n",
    "            cur = {num | p for p in pre} | {num}\n",
    "            ans |= cur\n",
    "            pre = cur\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        # import itertools\n",
    "        # res = []\n",
    "        # arr = [str(i) for i in arr]\n",
    "        # # print(arr)\n",
    "        # for i in range(1, len(arr)+1):\n",
    "        #     for j in range(len(arr) - (i-1)):\n",
    "        #         l = arr[j:j+i]\n",
    "        #         # print(l)\n",
    "        #         if len(l) == 1:\n",
    "        #             res.append(int(l[0]))\n",
    "        #         else:\n",
    "        #             # s = '|'.join(l)\n",
    "        #             # n = eval(s)\n",
    "        #             n = l[0]\n",
    "        #             for a in l[1:]:\n",
    "        #                 n |= a\n",
    "        #             res.append(n)\n",
    "        # # print(res)\n",
    "        # return len(set(res))\n",
    "        cur = set()\n",
    "        res = set()\n",
    "        for a in arr:\n",
    "            cur = {n | a for n in cur} | {a}\n",
    "            res |= cur\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        res, ans = set(), set()\n",
    "        for n in arr:\n",
    "            ans = {n | x for x in ans} | {n}\n",
    "            res |= ans\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        res, ans = set(), set()\n",
    "        for n in arr:\n",
    "            ans = {n | s for s in ans} | {n}\n",
    "            res |= ans\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        book = set()\n",
    "        result = 0\n",
    "        for i in range(n):\n",
    "            if(arr[i] not in book):\n",
    "                book.add(arr[i])\n",
    "                result += 1\n",
    "            for j in range(i-1,-1,-1):\n",
    "                if(arr[i] | arr[j] == arr[j]):\n",
    "                    break\n",
    "                arr[j] = arr[i] | arr[j]\n",
    "                if(arr[j] not in book):\n",
    "                    book.add(arr[j])\n",
    "                    result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        s = set()\n",
    "        pre = []\n",
    "        for i, v in enumerate(arr):\n",
    "            pre.append(v)\n",
    "            s.add(v)\n",
    "            for j in range(len(pre)-2, -1, -1):\n",
    "                s.add(pre[j])\n",
    "                if pre[j] == pre[j] | v:\n",
    "                    break\n",
    "                else:\n",
    "                    pre[j] |= v\n",
    "                    s.add(pre[j])\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        # 注意是按位或操作\n",
    "        \n",
    "        n = len(arr)\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            s.add(arr[i])\n",
    "            for j in range(i-1, -1, -1):\n",
    "                if (arr[i]|arr[j]) == arr[j]: break \n",
    "                arr[j] |= arr[i]\n",
    "                s.add(arr[j])\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = arr[:]\n",
    "        res_set = set()\n",
    "\n",
    "        for R in range(n):\n",
    "            res_set.add(dp[R])\n",
    "            for L in range(R - 1, -1, -1):\n",
    "                if (dp[L] | dp[R]) == dp[L]:\n",
    "                    break\n",
    "                dp[L] |= dp[R]\n",
    "                res_set.add(dp[L])\n",
    "\n",
    "        return len(res_set)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        res = set(arr)\n",
    "        am = list(arr)\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            am[i] = am[i + 1] | am[i]\n",
    "\n",
    "        for i in range(n):\n",
    "            a = arr[i]\n",
    "            for j in range(i + 1, n):\n",
    "                b = a | arr[j]\n",
    "                res.add(b)\n",
    "                a = b\n",
    "                if a == am[i]: break\n",
    "        \n",
    "        return len(res)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        dp = arr[:]         #仅仅为了尽量不破坏原数组\n",
    "        res_set = set()\n",
    "\n",
    "        for R in range(n):                      #以R为最后一位的区间\n",
    "            res_set.add(dp[R])\n",
    "            for L in range(R - 1, -1, -1):      #区间[L: R+1)的情况\n",
    "                if (dp[L] | dp[R]) == dp[L]:    #再往左，都不会再增大了  或的性质：只增不减 或的越多越大\n",
    "                    break                       #越往左，或得越多，越大\n",
    "                dp[L] |= dp[R]\n",
    "                res_set.add(dp[L])\n",
    "\n",
    "        return len(res_set)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        res = 0\n",
    "        sum_or = dict()\n",
    "        tmp = dict()\n",
    "        for i in arr:\n",
    "            l = list(tmp.items())\n",
    "            tmp = dict()\n",
    "            for k,v in l:\n",
    "                tmp[k|i] = v\n",
    "                sum_or[k|i] = v\n",
    "            tmp[i] = 1\n",
    "            sum_or[i] = 1\n",
    "        res = len(sum_or)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        res = 0\n",
    "        sum_or = dict()\n",
    "        tmp = dict()\n",
    "        for i in arr:\n",
    "            l = list(tmp.items())\n",
    "            tmp = dict()\n",
    "            for k,v in l:\n",
    "                tmp[k|i] = v\n",
    "                sum_or[k|i] = v\n",
    "            tmp[i] = 1\n",
    "            sum_or[i] = 1\n",
    "        print(sum_or)\n",
    "        res = len(sum_or)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subarrayBitwiseORs(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        dp=[set()]*n\n",
    "        res=set()\n",
    "        dp[0].add(arr[0])\n",
    "        res.add(arr[0])\n",
    "        for i in range(1,n):\n",
    "            tmp=set([arr[i]])\n",
    "            for j in dp[i-1]:\n",
    "                tmp.add(arr[i]|j)\n",
    "\n",
    "            res|=tmp\n",
    "            dp[i]=tmp\n",
    "        return len(res)                                    "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
